package number_93;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    private List<String> output = new ArrayList<>();
    private LinkedList<String> segments = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        backTrack(s, -1, 3);
        return output;
    }

    private void backTrack(String s, int prevPos, int dot) {
        int maxPos = Math.min(s.length() - 1, prevPos + 4);

        for (int currPos = prevPos + 1; currPos < maxPos; currPos++) {
            String segment = s.substring(prevPos + 1, currPos + 1);
            if (isValid(segment)) {
                segments.add(segment);
                if (dot - 1 == 0) {
                    addOutput(s, currPos);
                } else {
                    backTrack(s, currPos, dot - 1);
                }
                segments.removeLast();
            }

        }


    }

    private void addOutput(String s, int currPos) {
        String segment = s.substring(currPos + 1, s.length());
        if (isValid(segment)) {
            segments.add(segment);
            output.add(String.join(".", segments));
            segments.removeLast();
        }
    }


    private boolean isValid(String s) {
        int n = s.length();
        if (n > 3) {
            return false;
        }
        return s.charAt(0) == '0' ? n == 1 : Integer.parseInt(s) <= 255;
    }

    public static void main(String[] args) {
        new Solution().restoreIpAddresses("25525511125");
    }


}
